/*************************************************************************
	> File Name: backoff.c
	> Author: chen
	> Mail: chen_tmacy@foxmail.com
	> Created Time: 2015年01月07日 星期三 15时24分19秒
    > note: backoff.c演示了如何使用回退算法避免互斥量死锁。程序建立两个
    > 线程，一个lock_forward，一个lock_backward.每次循环都尝试锁住三个
    > 互斥量。lock_forward按照1 2 3顺序锁住三个互斥量。lock_backward
    > 按照相反的顺序锁互斥量。运行程序第一个参数是0，可能会出现死锁现象。
    > 很大程度上也可能不会发现死锁，因为每个线程运行时前一个线程可能就已经
    > 停止了。可以利用./a.out 1 1 。第二个参数是设置yield_flag来让线程交出
    > 运行权，让其他线程运行。会发生一些竞争现象。也可以./a.out 1 -1
    > 可以让线程睡眠1s，让出时间片给其他线程。
 ************************************************************************/

#include"errors.h"
#include<pthread.h>

#define ITERATIONS 10  // 线程重复循环次数

// 初始化互斥量的静态数组

pthread_mutex_t mutex[3] = {
    PTHREAD_MUTEX_INITIALIZER,
    PTHREAD_MUTEX_INITIALIZER,
    PTHREAD_MUTEX_INITIALIZER,
};

int backoff = 1; // backoff 或者 deadlock
int yield_flag = 0;

void *lock_forward(void* arg){
    int i ,iterate,backoffs;
    int status;

    for(iterate = 0;iterate < ITERATIONS;iterate++){
        backoffs = 0;
        for(i = 0;i < 3;i++){
            if(0 == i){
                if((status = pthread_mutex_lock(&mutex[i]))){
                    err_abort(status,"First lock");
                } 
            }else{
                if(backoff){
                    status = pthread_mutex_trylock(&mutex[i]);
                }else{
                    status = pthread_mutex_lock(&mutex[i]);
                }
                if(status == EBUSY){
                    backoffs++;
                    DPRINTF(("(forward locker backing off at d)\n",i));
                    for(;i >= 0;i--){
                        if((status = pthread_mutex_unlock(&mutex[i]))){
                            err_abort(status,"Backoff");
                        }
                    }
                }else if(status != 0){
                    err_abort(status,"Lock mutex");
                    DPRINTF(("forward locker got %d \n",i));
                }
            }
            if(yield_flag){
                if(yield_flag > 0){
                    sched_yield();
                }else{
                    sleep(1);
                }
            }
        }

        printf("lock forward got all locks,%d backoffs\n",backoffs);
        pthread_mutex_unlock(&mutex[2]);
        pthread_mutex_unlock(&mutex[1]);
        pthread_mutex_unlock(&mutex[0]);
        sched_yield();
    }
    return NULL;
}

void *lock_backward(void *arg){
    int i,iterate,backoffs;
    int status;

    for(iterate = 0;iterate < ITERATIONS; iterate++){
        backoffs = 0;
        for(i = 2;i >= 0;i--){
            if(2 == i){
                if((status = pthread_mutex_lock(&mutex[i]))){
                    err_abort(status,"First lock");
                }
            }else{
                if(backoff){
                   status = pthread_mutex_trylock(&mutex[i]);
                }else{
                    status = pthread_mutex_lock(&mutex[i]);
                }
                if(status == EBUSY){
                    backoffs++;
                    DPRINTF(("backward locker backing off at %d \n",i));
                    for(;i < 3;i++){
                        if ((status = pthread_mutex_unlock(&mutex[i]))){
                            err_abort(status ,"Backoff");
                        }
                    }
                }else if (status){
                    err_abort(status,"Lock mutex");
                    DPRINTF(("backward locker got %d\n",i));
                }
            }
            if(yield_flag){
                if(yield_flag > 0)
                    sched_yield();
                else
                    sleep(1);
            }
        }

        printf("lock backward got all locks ,%d backoffs\n",backoffs);
        pthread_mutex_unlock(&mutex[0]);
        pthread_mutex_unlock(&mutex[1]);
        pthread_mutex_unlock(&mutex[2]);
        sched_yield();
    }
    return NULL;
}

int main(int argc,char *argv[]){
    pthread_t forward,backward;
    int status;

    if(argc > 1){
        backoff = atoi(argv[1]);
    }

    if(argc > 2){
        yield_flag = atoi(argv[2]);
    }

    if((status = pthread_create(&forward,NULL,lock_forward,NULL))){
        err_abort(status,"Created froward");
    }

    if((status = pthread_create(&backward,NULL,lock_backward,NULL))){
        err_abort(status,"Created backward");
    }

    pthread_exit(NULL);
    return 0;
}

